#include <stdio.h>
// 队列是先进先出（FIFO）的数据结构
#define MAX_SIZE 100
typedef int ElementType; // 元素类型

// 队列结构体
typedef struct {
    ElementType data[MAX_SIZE]; // 数据数组
    int front; // 头指针
    int rear; // 尾指针
} Queue;    

// 初始化队列
void InitQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
}

//判断队列是否为空
ElementType IsEmpty(Queue* q) {
    if (q->front == q->rear)
    {
        printf("队列为空\n");
        return 1;
    }
    else
    {
        return 0;
    }   
}

//出队(删除元素)
ElementType Dequeue(Queue* q) {
    if (IsEmpty(q)) return 0;
    ElementType value = q->data[q->front];
    q->front++;
    return value;
}

//判断队列是否已满
/*
入队时，不能单看rear是否>=MAX_SIZE来判断队列是否已经满了。
因为有可能rear==MAX_SIZE了，但是前面有元素出队了，导致队头前面还有空间
所以入队时需要做判断。
口口口口口口口口口口  MAX_SIZE = 10
    ^            ^
  front         rear
如上图，，此时明显队头前面还有空间，所以需要挪动数据，腾出空间
口口口口口口口口口口  MAX_SIZE = 10
^            ^
front       rear
这样，就可以在队尾插入数据了 
*/
ElementType queueFull(Queue* q){
    if(q->front > 0) // 判断队头前面有无空位，>0意味着有元素出队了，队头前面有空位。
    {
        int step = q->front;  // 记录当前队列的有效元素个数
        for (int i = q->front; i <= q->rear; i++) { // 移动数据
            q->data[i - step] = q->data[i]; // 将数据向前移动
    }
    q->front = 0; // 重置头指针
    q->rear = q->rear - step; // 更新尾指针
    return 1;
}
    else{
        printf("队列已满\n");
        return 0;
    }
}

//入队(添加元素)
ElementType Enqueue(Queue* q, ElementType value) {
    if (q->rear >= MAX_SIZE)
    {
        if(!queueFull(q)){  // 队满（1是True，0是Flase）
            return 0;
        }
    }
    q->data[q->rear] = value;
    printf("当前入队元素：%d\n",q->data[q->rear]);
    q->rear++;
    return 1;
}

//获取队头数据
int getHead(Queue *q,ElementType *e)
{
    if (q->front == q->rear)
    {
        printf("空队列\n");
        return 0 ;
    }
    *e = q->data[q->front];
    printf("队头数据为：%d", *e);
    return *e;
}

int main() {
    Queue q;
    InitQueue(&q);
    Enqueue(&q, 1);
    Enqueue(&q, 2);
    Enqueue(&q, 3);
    printf("出队元素: %d\n", Dequeue(&q));
    printf("出队元素: %d\n", Dequeue(&q));
    printf("出队元素: %d\n", Dequeue(&q));
    Enqueue(&q, 3);
    Enqueue(&q, 2);
    Enqueue(&q, 1);
    int a;
    getHead(&q, &a);
    return 0;
}
